package mo.golden;

import java.util.*;

public class L04_01 {

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        Map<Integer, Queue<Integer>> path = new HashMap<>();
        for (int[] edge : graph) {
            Queue<Integer> targets = path.getOrDefault(edge[0], new LinkedList<>());
            targets.add(edge[1]);
            path.put(edge[0], targets);
        }
        Queue<Integer> targets = path.get(start);
        if (targets == null) {
            return false;
        }
        boolean[] visited = new boolean[n];
        while (!targets.isEmpty()) {
            Integer node = targets.poll();
            if (node == target) {
                return true;
            } else {
                if (!visited[node]) {
                    if (path.get(node) != null) {
                        targets.addAll(path.get(node));
                    }
                }
            }
            visited[node] = true;
        }
        return false;
    }

    public static void main(String[] args) {
        L04_01 test = new L04_01();
        System.out.println(test.findWhetherExistsPath(25, new int[][]{{0, 1}, {1, 12}}, 0, 12));
    }
}
